1. Field of the Invention
This invention relates to non-volatile memory storage systems, and more particularly to wear-leveling, caching, and re-mapping of flash memory.
2. Description of the Related Art
Non-volatile semiconductor memory is useful for relatively long-term storage in computer systems. Often the computer's hard disk is replaced by an array of non-volatile random-access memories (NVRAM's) or non-volatile flash memories. Battery-backed DRAM is sometimes used. These memory devices use electrically-erasable programmable read-only-memory (EEPROM) technology for storage cells. Floating polysilicon gates in these storage cells retain charge and state when power is lost, providing non-volatile storage.
Flash EEPROM chips are divided into pages and blocks. A 64 Mbit flash chip typically has 512-byte pages which happens to match the sector size for IDE and SCSI hard disks. Rather than writing to just one word in the page, the entire page must be written at the same time; individual bytes cannot be written. The page must be cleared of any previous data before being written; clearing is accomplished by a flash erase cycle. An entire block pages (typically 16 pages) is erased at once. Thus a block of 16 pages must be erased together, while all 512 bytes on a page must be written together. EEPROM memory cells are not as reliable as static or dynamic RAM cells. Indeed, one or two percent of the pages on a new flash chip are usually defective when sold to the customer. EEPROM cells wear out as they are written and erased because some charge is trapped in the insulating oxide layers surrounding the floating gate. Eventually this trapped charge increases until it prevents an applied voltage from sufficiently reading the cell. Thus a scheme is needed to identify such defective memory cells and replace them with good cells.
FIG. 1 is a prior-art replacement scheme for re-mapping defective pages of flash memory. Flash chip 10 has a memory array of EEPROM cells arranged into pages. Each page contains a 512-byte data field 12, and an additional 16-byte pointer field 14. Pointer field 14 contains a re-map bit (not shown) that is set when a defect is found in any of the 512 bytes of data in the page. When a page is read, the re-map bit is also read to determine if the page is defective. If defective, a pointer to another page is read from pointer field 14. The new page pointed to contains the replaced data.
For example, page 1 of FIG. 1 is defective. When page 1 at address 001 is read and found to be defective, pointer field 14 is also read. Pointer field 14 for page 1 contains the pointer 110. The address is changed to 110 so that the replacement page at address 110 is read to obtain the data for page 1. Thus address 001 to page 1 is re-mapped by pointer field 14 to replacement page 6 at address 110. Page 6 was initially reserved as a spare page for later replacement of a defective page.
An extra read of the flash memory may be necessary to read the bad data with the pointer. Another problem with using pointer field 14 for re-mapping is that the 16 bytes of the pointer field must be good. When a defect occurs in the data field 12 of a page, and in pointer field 14, then the defective page cannot be re-mapped and bad data can be read. It is thus critical that the pointer field 14 contain good memory cells.
FIG. 2 shows a prior-art re-mapping scheme using a bit-map table. To work around the problems of using the pointer fields in the flash memory pages, a separate re-map table in SRAM is used. SRAM re-map table 15 is accessed when the flash memory chip is accessed. Most logical addresses are simply passed through without translation or re-mapping since the corresponding bit in re-map table 15 is a zero. However, when a logical address's entry in re-map table 15 is a one, the logical address is re-mapped to a different physical address so that a replacement page is accessed.
When a one is encountered when reading re-map table 15, a separate address re-map table (not shown) is consulted to find the physical address. This address re-map table is typically stored in the last block of each flash device. Unfortunately, this scheme requires that the last block of the flash device is defect-free and not wear out; otherwise the address re-map table can re-map to the wrong page.
More complex re-mapping or address translation tables have been used with flash memory devices. Assar et al. in U.S. Pat. Nos. 5,479,638, and 5,485,595, assigned to Cirrus Logic of Fremont, Calif., teaches a content-addressable memory for a re-map table, using CAM, EEPROM, DRAM, or SRAM cells. This table includes an erase counter field which is incremented as a page is erased and written. Once a page reaches a threshold erase count, it is moved to an unused page. Once all unused pages are depleted, a clean-out erase cycle is performed to clear all erase counters to zero. The process then repeats. Thus the wear on pages of flash memory is spread out or leveled among all pages.
Periodically clearing the erase counters is undesirable because there is no way to determine the total number of erase/write cycles to a given block of flash memory. Some blocks can be use heavily while others are lightly used; yet their erase counters are periodically cleared to zero regardless of the usage. Thus while wear-leveling occurs between erase-counter clears, longer-term wear leveling beyond the erase-counter clears is not performed.
Not periodically clearing the erase counters allows the total number of erase/writes to be stored, but then pages can be swapped unnecessarily when their erase counts hover around the threshold. This thrashing of pages is similar to the problem seen in processor caches.
Other flash memory systems with wear-leveling are taught by Kaki et al. in U.S. Pat. No. 5,530,828, assigned to Hitachi of Tokyo, Japan, and Harari et al. in U.S. Pat. No. 5,602,987, assigned to SanDisk Corp. of Sunnyvale, Calif. Kaki et al. use a management table with a counter that counts bytes written as the 512 bytes are written to a page. Harari et al. uses a data cache to buffer writes to the flash memory and reduce the total number of writes to flash.
While these flash memory systems are useful, a more effective flash memory system is desired. A more efficient and exact wear-leveling scheme is desired. It is desired to minimize excess writes to flash memory while re-mapping addresses to pages of flash memory. A unified table for re-mapping, wear-leveling, and caching flash memories is desirable.